#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back

using namespace std;

using pii = pair < int , int >;
using vec = vector < int >;
using veg = vector < pii >;
using ll = long long;
using db = double;

int read() {
    int x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = x * 10 + (ch ^ 48),ch = getchar(); return f ? -x : x;
}

const int N = 1e5 + 10;

int a[N],n,r1[N],r2[N],l1[N],l2[N];
ll ans,s[N];

namespace seg {
	struct node { ll lmx,rmx; ll s; } val[N << 2];
	node operator + (node a,node b) { node c; c.s = a.s + b.s; c.lmx = max(a.lmx,b.lmx + a.s); c.rmx = max(b.rmx,a.rmx + b.s); return c; }
	void build(int o = 1,int l = 1,int r = n) {
		if(l == r) return val[o].lmx = val[o].rmx = max(a[l],0),val[o].s = a[l],void(); int mid = l + r >> 1;
		build(o << 1,l,mid); build(o << 1 | 1,mid + 1,r); val[o] = val[o << 1] + val[o << 1 | 1];
	}
	node query(int xl,int xr,int o = 1,int l = 1,int r = n) {
		if(xl == l && xr == r) return val[o]; int mid = l + r >> 1;
		if(xr <= mid) return query(xl,xr,o << 1,l,mid); else if(xl > mid) return query(xl,xr,o << 1 | 1,mid + 1,r);
		else return query(xl,mid,o << 1,l,mid) + query(mid + 1,xr,o << 1 | 1,mid + 1,r);
	}
}

void solve() {
	n = in; for(int i = 1;i <= n;i++) a[i] = in;
	ans = 0;
	static int stk1[N],stk2[N],stk3[N]; int top1 = 0,top2 = 0,top3 = 0; 
	for(int i = 1;i <= n;i++) s[i] = s[i - 1] + a[i],l1[i] = l2[i] = 0,r1[i] = r2[i] = n + 1;
	seg :: build();
	for(int i = 1;i <= n;i++) {
		top3 = 0; 
		while(top2 && a[i] > a[stk2[top2]]) r2[stk2[top2]] = i,top2--;
		while(top1 && a[i] >= a[stk1[top1]]) r1[stk1[top1]] = i,stk3[++top3] = stk1[top1],top1--;
		for(int j = top3;j >= 1;j--) stk2[++top2] = stk3[j];
		stk1[++top1] = i;
	}
	top1 = top2 = 0;
	for(int i = n;i >= 1;i--) {
		top3 = 0;
		while(top2 && a[i] > a[stk2[top2]]) l2[stk2[top2]] = i,top2--;
		while(top1 && a[i] >= a[stk1[top1]]) l1[stk1[top1]] = i,stk3[++top3] = stk1[top1],top1--;
		for(int j = top3;j >= 1;j--) stk2[++top2] = stk3[j];
		stk1[++top1] = i;
	}
	for(int i = 1;i <= n;i++) {
		int p1 = l1[i],L = l2[i],p2 = r1[i],R = r2[i];
		//cerr << l2[i] << " " << l1[i] << " " << i << " " << r1[i] << " " << r2[i] << endl;
		if(p1 > 0) {
			ll res = s[i - 1] - s[p1];
			int posr = (p2 <= n && a[p2] == a[i]) ? R : p2;
			res += i + 1 <= posr - 1 ? seg :: query(i + 1,posr - 1).lmx : 0;
			res += L + 1 <= p1 - 1 ? seg :: query(L + 1,p1 - 1).rmx : 0;
			ans = max(ans,res);
			//	cerr << res << endl;
		}
		if(p2 <= n) {
			ll res = s[p2 - 1] - s[i];
			int posl = (p1 > 0 && a[p1] == a[i]) ? L : p1;
			res += posl + 1 <= i - 1 ? seg :: query(posl + 1,i - 1).rmx : 0;
			res += p2 + 1 <= R - 1 ? seg :: query(p2 + 1,R - 1).lmx : 0;
			ans = max(ans,res);
			//	cerr << res << endl;
		}
	}
	printf("%lld\n",ans);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    for(int T = in;T;T--) solve();
}
